{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bubble Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def bubble_sort(array):\n",
    "    n=len(array)\n",
    "    for i in range(0,n):\n",
    "        for j in range(0,n-i-1):\n",
    "            if array[j] > array[j + 1]:\n",
    "                array[j], array[j + 1] = array[j + 1], array[j] # swap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Optimized Bubble Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# optimized bubble sort does not increase or decrease asymtotic notations\n",
    "# however number of iterations can be reduced to some extent\n",
    "def optimized_bubble_sort(array):\n",
    "    global iterations\n",
    "    iterations = 0\n",
    "    for i in range(len(array) - 1):\n",
    "        swapped = False\n",
    "        for j in range(len(array) - 1):\n",
    "            iterations += 1\n",
    "            if array[j] > array[j + 1]:\n",
    "                array[j], array[j + 1] = array[j + 1], array[j]\n",
    "                swapped = True\n",
    "        # if no swapping is performed that means sorting is complete\n",
    "        # hence break out of the loop\n",
    "        if not swapped:          \n",
    "            break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Time Complexity:\n",
    "\n",
    "- Best Case: O(n)\n",
    "- Average Case: O(n * n)\n",
    "- Worst Case:  O(n * n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Code for executing and seeing the difference in time complexities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Best Case Performance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "18\n"
     ]
    }
   ],
   "source": [
    "# elements are already sorted\n",
    "array = [i for i in range(1, 20)]\n",
    "\n",
    "optimized_bubble_sort(array)\n",
    "# 20 ALREADY sorted elements need 18 iterations approx = n\n",
    "print(iterations)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Average Case Performance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "324\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "# elements are randomly shuffled\n",
    "array = [i for i in range(1, 20)]\n",
    "random.shuffle(array)\n",
    "\n",
    "optimized_bubble_sort(array)\n",
    "# 20 shuffled elements need 324 iterations approx = n * n\n",
    "print(iterations)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Worst Case Performance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "324\n"
     ]
    }
   ],
   "source": [
    "# elements are reverse sorted\n",
    "array = [i for i in range(1, 20)]\n",
    "# reversing the array\n",
    "array = array[::-1]\n",
    "\n",
    "optimized_bubble_sort(array)\n",
    "# 20 REVERSE sorted elements need 324 iterations approx = n * n\n",
    "\n",
    "print(iterations)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Applications"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When you're doing something quick and dirty and for some reason you can't just use the standard library's sorting algorithm. The only advantage this has over insertion sort is being slightly easier to implement."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
